/*
    7. Write a C program to sort a list of elements using the quick sort algorithm. 
    Quick sort is a comparison sort, meaning that it can sort items of any type for
    which a "less-than" relation (formally, a total order) is defined.
    Note: Read n values into array and Sort using Quick Sort
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void printarrayany(int a[], int head, int end)
{
    int i;
    for(i = head; i <= end; i++){
        printf("%d, ", a[i]);
    }
    printf("\n");
}

void printarray(int a[], int len)
{
    printarrayany(a, 0, len - 1);
}

int divarray(int a[], int head, int end)
{
    if(head >= end){
        return head;
    }
    int len = end + 1 - head;
    int *tmpa = (int *)malloc(len * sizeof(int));
    int i = head + 1;
    int j = 0; 
    int k = len - 1;
    int ref = a[head];

    while(j < k){
        if(a[i] < ref){
            tmpa[j++] = a[i++];
        }else{
            tmpa[k--] = a[i++];
        }
        if(k == j){
            tmpa[k] = a[head];
        }        
    }

    memcpy(&a[head], tmpa, len * sizeof(int));    
    free(tmpa);
    return (head + k);
}

void quicksort(int a[], int head, int end)
{
    //printf("h = %d, e = %d\n", head, end);
    if(head >= end){
        return;
    }
    int m = divarray(a, head, end);
    //printf("m = %d\n", m);
    //printarrayany(a, head, end);
    
    quicksort(a, head, m - 1);
    quicksort(a, m + 1, end);        
}

int main(void)
{
    int len;
    int i;
    printf("Input the size of array : ");
    scanf("%d", &len);
    int *a = (int *)malloc(len * sizeof(int));
    for(i = 0; i < len; i++){
        scanf("%d", &a[i]);
    }
    quicksort(a, 0, len - 1);
    printf("After quick sort : \n");
    printarray(a, len);

    return 0;
}